#include <bits/stdc++.h>
using namespace std;

/*
2163. 删除元素后和的最小差值
已解答
困难
相关标签
premium lock icon
相关企业
提示
给你一个下标从 0 开始的整数数组 nums ，它包含 3 * n 个元素。

你可以从 nums 中删除 恰好 n 个元素，剩下的 2 * n 个元素将会被分成两个 相同大小 的部分。

前面 n 个元素属于第一部分，它们的和记为 sumfirst 。
后面 n 个元素属于第二部分，它们的和记为 sumsecond 。
两部分和的 差值 记为 sumfirst - sumsecond 。

比方说，sumfirst = 3 且 sumsecond = 2 ，它们的差值为 1 。
再比方，sumfirst = 2 且 sumsecond = 3 ，它们的差值为 -1 。
请你返回删除 n 个元素之后，剩下两部分和的 差值的最小值 是多少。

 

示例 1：

输入：nums = [3,1,2]
输出：-1
解释：nums 有 3 个元素，所以 n = 1 。
所以我们需要从 nums 中删除 1 个元素，并将剩下的元素分成两部分。
- 如果我们删除 nums[0] = 3 ，数组变为 [1,2] 。两部分和的差值为 1 - 2 = -1 。
- 如果我们删除 nums[1] = 1 ，数组变为 [3,2] 。两部分和的差值为 3 - 2 = 1 。
- 如果我们删除 nums[2] = 2 ，数组变为 [3,1] 。两部分和的差值为 3 - 1 = 2 。
两部分和的最小差值为 min(-1,1,2) = -1 。
示例 2：

输入：nums = [7,9,5,8,1,3]
输出：1
解释：n = 2 。所以我们需要删除 2 个元素，并将剩下元素分为 2 部分。
如果我们删除元素 nums[2] = 5 和 nums[3] = 8 ，剩下元素为 [7,9,1,3] 。和的差值为 (7+9) - (1+3) = 12 。
为了得到最小差值，我们应该删除 nums[1] = 9 和 nums[4] = 1 ，剩下的元素为 [7,5,8,3] 。和的差值为 (7+5) - (8+3) = 1 。
观察可知，最优答案为 1 。
 

提示：

nums.length == 3 * n
1 <= n <= 105
1 <= nums[i] <= 105
*/

// 法一
class Solution {
public:
    using ll = long long;
    long long minimumDifference(vector<int>& nums) {
        // 数组长度为3n，计算n的值
        int n = nums.size() / 3;
        
        // 前缀处理：计算前i+1个元素中选择n个的最小和
        vector<ll> prefix_min(3 * n, LLONG_MAX);
        // 最大堆：维护当前最小的n个元素
        priority_queue<int> max_heap;
        ll sum = 0;
        for (int i = 0; i < 3 * n; i++) {
            max_heap.push(nums[i]);
            sum += nums[i];
            // 堆大小超过n时，弹出最大元素，保留最小的n个元素
            if (max_heap.size() > n) {
                sum -= max_heap.top();
                max_heap.pop();
            }
            // 堆大小为n时，记录当前最小和
            if (max_heap.size() == n) {
                prefix_min[i] = sum;
            }
        }

        // 后缀处理：计算从i到末尾的元素中选择n个的最大和
        vector<ll> suffix_max(3 * n, LLONG_MIN);
        // 最小堆：维护当前最大的n个元素
        priority_queue<int, vector<int>, greater<int>> min_heap;
        sum = 0;
        // 从后向前遍历，确保处理每个位置及其之后的元素
        for (int i = 3 * n - 1; i >= 0; i--) {
            min_heap.push(nums[i]);
            sum += nums[i];
            // 堆大小超过n时，弹出最小元素，保留最大的n个元素
            if (min_heap.size() > n) {
                sum -= min_heap.top();
                min_heap.pop();
            }
            // 堆大小为n时，记录当前最大和
            if (min_heap.size() == n) {
                suffix_max[i] = sum;
            }
        } 

        // 遍历所有可能的分割点m（n-1 ≤ m ≤ 2n-1）
        // 确保前缀部分和后缀部分各包含n个元素
        ll ans = LLONG_MAX;
        for (int m = n - 1; m <= 2 * n - 1; m++) {
            // 确保前后缀均有效
            if (prefix_min[m] != LLONG_MAX && suffix_max[m + 1] != LLONG_MIN) {
                ans = min(ans, prefix_min[m] - suffix_max[m + 1]);
            }
        }

        return ans;
    }
};

// 法二
class Solution {
public:
    long long minimumDifference(vector<int>& nums) {
        int n = nums.size() / 3;
        long long ans = 1e18;

        // 处理第一部分：前缀最小和
        vector<long long> prefix_min(3 * n, 1e18);
        priority_queue<int> max_heap;  // 大顶堆
        long long current_sum = 0;
        
        // 计算前缀最小和
        for (int i = 0; i < 3 * n; ++i) {
            max_heap.push(nums[i]);
            current_sum += nums[i];
            // 维护堆大小为n
            if (max_heap.size() > n) {
                current_sum -= max_heap.top();
                max_heap.pop();
            }
            // 堆大小为n时记录
            if (max_heap.size() == n) {
                prefix_min[i] = current_sum;
            }
        }
        
        // 处理第二部分：后缀最大和
        vector<long long> suffix_max(3 * n, -1e18);
        priority_queue<int, vector<int>, greater<int>> min_heap;  // 小顶堆
        current_sum = 0;
        
        // 计算后缀最大和
        for (int i = 3 * n - 1; i >= 0; --i) {
            min_heap.push(nums[i]);
            current_sum += nums[i];
            // 维护堆大小为n
            if (min_heap.size() > n) {
                current_sum -= min_heap.top();
                min_heap.pop();
            }
            // 堆大小为n时记录
            if (min_heap.size() == n) {
                suffix_max[i] = current_sum;
            }
        }
        
        // 遍历所有可能的分割点
        for (int m = n - 1; m < 2 * n; ++m) {
            if (prefix_min[m] != 1e18 && suffix_max[m + 1] != -1e18) {
                ans = min(ans, prefix_min[m] - suffix_max[m + 1]);
            }
        }
        return ans;
    }
};

// 自定义堆  减少性能开销
// 法三 这两个月以来最优雅的一次
using ll = long long;
constexpr int N = 1e5 + 5; /* 题目数据nums.length == 3 * n
                                        1 <= n <= 10^5
                                        1 <= nums[i] <= 10^5
                                        */
ll suf[N * 2];      // 后缀最大值  下标范围 0~3n - 1

namespace sc {
    // 肯定比std的性能更优化 没有那么多冗余
    template<class _Tp, class _Comp = less<_Tp>>
    struct priority_queue {
        // 静态堆 性能要优化一点 没有动态缓存 [b,e]的范围
        priority_queue(_Tp* b, _Tp* e) : b_(b), e_(e) {
            make_heap(b_, e_, _Comp{});
            // 谓词决定是最大还是最小堆
        }

        void pop() {
            pop_heap(b_, e_, _Comp{});
            e_--;
        }
        void push(_Tp tmp) {
            *e_++ = tmp;
            push_heap(b_, e_, _Comp{});
        }
        _Tp top() const {
            return *b_;
        }

        // 相关字段 
        _Tp c_[N * 2];      // static 避免new的动态开销
        _Tp* b_ = c_;       // 指向堆的起始指针
        _Tp* e_ = c_;       // 指向堆的末尾指针
    };
}       // namespace sc

class Solution {
public:
    long long minimumDifference(vector<int>& nums) {
        // 数组首地址就给堆的首指针
        int* start = nums.data();
        int n3 = nums.size(), n1 = n3 / 3, n2 = n1 * 2;

        ///////////////////////  后缀预处理  /////////////////////
        // 初始化 最后n个元素 [start + n2, start + n3] 最小堆来管理最大的n个元素
        sc::priority_queue<int, greater<int>> suf_heap(start + n2, start + n3);
        ll sufs = accumulate(start + n2, start + n3, 0LL);
        suf[n2] = sufs;         // 记录位置n2的suffixSum  也就是最后n个元素的和

        // 从后往前  必须有n个元素
        for (int i = n2 - 1; i >= n1; i--) {
            int cur = start[i];
            // 当前元素的比堆中的最小元素大  那就换了 保证总和最大 
            if (cur > suf_heap.top()) {
                sufs += cur - suf_heap.top();
                // 替换 更新
                suf_heap.pop();
                suf_heap.push(cur);
            }
            // 记录位置 
            suf[i]  = sufs;
        }

        ///////////////////////  前缀预处理   //////////////////////
        // 类似后缀预处理 只不过sort倒转过来
        sc::priority_queue<int> pre_heap(start, start + n1);
        ll pres = accumulate(start, start + n1, 0LL);

        ll ans = pres - suf[n1];

        // 前缀就是从前往后了  n1~n2 - 1
        for (int i = n1; i < n2; i++) {
            int cur = start[i];
            // 当前元素比最大的小 就也替换
            if (cur < pre_heap.top()) {
                pres += cur - pre_heap.top();
                pre_heap.pop();
                pre_heap.push(cur); 
            }
            // 前缀和 - 后缀和  = 差值的最小值
            ans = min(ans, pres - suf[i + 1]);
        }
        return ans;
    }
};